The present invention relates generally to garbage collection mechanisms that automatically recover memory that is no longer in use by an operating system nor application programs in a computer system, and more particularly to a system and method for reducing computational overhead associated with such garbage collection mechanisms.
Modern programming systems that support object-oriented data models often provide automatic storage management, thereby freeing the programmer from the requirement of explicitly requesting storage for data from the system, and, more importantly, offering storage when it is no longer needed. The latter requirement has historically been the source of many and the most troublesome program bugs. Automatic recovery of storage no longer in use is often referred to as garbage collection.
Garbage collection is a complex topic that has been the subject of many technical articles and at least one text book. The following is a simplified explanation of dynamic memory allocation and garbage collection. For a more detailed discussion of basic garbage collection technology, see, for example, Richard Jones and Rafael Lins, xe2x80x9cGarbage Collection,xe2x80x9d John Wiley and Sons Ltd., 1996, U.S. Pat. Nos. 5,088,036, and 5,930,807, all of which are incorporated by reference in their entirety.
Referring to FIG. 1, there is shown a typical computer system 100 having a central processing unit (CPU) 102, user interface 106, and main memory 108. The main memory 108 stores an operating system 110 and one or more application programs 112 (one shown). The operating system 110 and application programs 112 comprise processes (also called threads or tasks) that include program code and data (such as constants, local variables and other parameters) used in the execution of the program code. In addition, the main memory 108 stores at least one heap 116 used for dynamic memory allocation. The space in main memory 108 allocated to store the operating system 110, application programs 112, and the heap 116 need not be contiguous. For example, pages or possibly larger contiguous chunks of main memory can be typically linked together using tables or other well known prior art mechanisms.
The program code and data stored in main memory 108 refers to objects. The term xe2x80x9cobjectxe2x80x9d is herein defined to mean any data structure created by a process. The heap 116 stores such objects. More specifically, when a process spawns an object, a memory allocation routine 118 in the operating system is called. The memory allocation routine 118 responds by allocating a region in the heap 116 for storing the object.
The representation of the object in the heap may vary. In object-oriented programming systems, for example, an object typically contains the variables declared in the object""s class and all of the object""s super classes. It should be noted that the heap 116 may store additional information related to the objects, the details of which are not relevant to the present invention.
The program code and associated data stored in main memory 108 use a reference to point to the representation of a given object in the heap 116. Such a reference is referred to herein as an xe2x80x9cobject reference.xe2x80x9d The object reference maybe direct or indirect. A direct object reference identifies the location in main memory for the object (for example, the location in main memory of the header of the object). On the other hand, an indirect object reference points to an object handle, which can be used to locate the location in main memory for the object. In this document, the term object reference refers to both direct and indirect object references.
The memory allocation routine 118 discussed above may occur repeatedly. Clearly, if this routine continued unabated, all of the space in the heap 116 would be exhausted. Therefore, space in the heap 116 must be restored by either explicit action of the program, or some other mechanism.
The solution to this problem is to recover blocks of memory space in the heap 116 that are no longer being used by the active processes. Garbage collection is a term that refers to automatic methods of recovering unused memory in the heap 116. Garbage collection is based on the fact that if no pointer to a heap object exists anywhere in the executing environment of a program, the object can never again be accessed and therefore the storage occupied by the object can be reused for another object. Garbage collection comprises the identification of all reachable objects, i.e., those that can be accessed by the executing program. All reachable objects are identified by marking all objects pointed to by the roots of a programs (i.e., local variables and static variables) and all objects pointed to by objects pointed to by roots, recursively, until all reachable objects have been identified. Reached objects are considered xe2x80x9clivexe2x80x9d and are kept. Objects which are not reached are considered xe2x80x9cdeadxe2x80x9d and their storage space is made available for future allocations.
A garbage collection routine 120 typically gathers and recovers unused memory upon the occurrence of a predefined event, such as the expiration of a predetermined time period or the available heap memory reaches a predefined threshold. A large number of different garbage collection methodologies have been proposed. For a discussion of the state of the art, see, for example, Jones and Lin, xe2x80x9cGarbage Collection, xe2x80x9d John Wiley and Sons Ltd, 1996, incorporated by reference in its entirety above.
One way to make garbage collection more efficient, and to reduce the length of system pauses caused by garbage collection, is to reduce the number of objects that need to be processed during a given garbage collection cycle using a generational garbage collection scheme. Generational schemes are based on the observations that most objects have short lifetimes, dying shortly after they are allocated, and that objects which do not die quickly and have been reachable for some time will continue to be reachable (i.e. live). Generational schemes partition the objects in the heap into groups called xe2x80x9cgenerations,xe2x80x9d based upon the ages of the objects, where an object""s age is typically measured in terms of the number of garbage collections that the object has survived. For this discussion, consider two generations, a xe2x80x9cyoungxe2x80x9d generation of recently allocated objects, and an xe2x80x9coldxe2x80x9d generation of objects which have survived some minimum number of collections. Typically, the young generation is much smaller than the older generations.
Generational schemes perform frequent collections of the young generation, and only occasionally do full collections of the entire heap. Typically, generational schemes perform a minor garbage collection upon the occurrence of a predefined event (such as the expiration of a predetermined time period or the available heap memory reaches a predefined threshold). The minor garbage collection routine identifies younger generation objects that are not reachable from the objects stored in the heap, and identifies the space in the heap previously allocated to one or more of these objects as a candidate for reclamation. Less frequently, a major garbage collection routine is performed that identifies all objects that are not reachable from the objects stored in the heap, and identifies the space in the heap previously allocated to one or more of these objects as a candidate for reclamation.
FIG. 2 shows a system in which the heap 116 has been logically divided into three generations: Generation 0 stores the youngest objects, Generation 1 stores objects that have persisted for at least N garbage collection cycles (where N is typically a value between 1 and 4), and Generation 2 stores the oldest objects in the system. The simplest policy is to advance all live objects from one generation to the next oldest generation each time a generational garbage collection is performed. Another technique is to divide the youngest generation into an object creation space and an aging space. Objects are initially allocated in the creation space. The aging space holds survivors from the creation space. Objects are promoted to the next older generation only after surviving N garbage collection cycles.
One of the biggest problems with generational garbage collectors is handling inter-generation object references whereby the only reference(s) to an object in one generation may be stored in object(s) in another generation. FIG. 2 shows a number of inter-generational references 170. If the only reference to an object is an inter-generational reference, or more generally, if the only path from a root set reference to an object requires traversal of an inter-generation object reference, the object would be improperly deleted by the garbage collection routine unless all inter-generational references were taken into account during garbage collection. However, scanning the older generation heap areas for inter-generational references each time a younger generation heap area is garbage collected would take away some of the efficiency achieved by using generational garbage collection.
If scanning older generations during collection of younger generations is ruled out as too inefficient, then another mechanism has to be developed to keep track of references in older generation objects that point to newer generation objects. One such mechanism utilizes a xe2x80x9cremembered setxe2x80x9d that identifies (for example, by storing a pointer to) each older generation object that contains a reference to a younger generation object. In this scheme, at every store operation, a software procedure (typically referred to as a xe2x80x9cwrite barrierxe2x80x9d) ensures that the updated location is stored in the remembered set if the store creates a reference from an older generation object to a younger generation object.
The remembered set is obtained by monitoring, by software or hardware means, the execution of the processes in such a way that all stores of pointers to new objects into old objects can be discovered. Such old objects become members of the remembered set, which is used during the next and subsequent minor garbage collections.
More specifically, in the next and subsequent minor garbage collections, the members of the remembered set are treated as part of the root set of object references from which the set of reachable younger generation objects is generated. Those younger generation objects that are not part of this set are identified as younger generation objects that are not reachable from the objects stored in the heap, and the space in the heap previously allocated to one or more of these unreachable objects is identified as a candidate for reclamation.
Various schemes have been proposed to monitor stores into old objects so that they can be identified and the remembered set updated accordingly. The modified old objects are scanned to determine if they contain pointers to young objects. Recording the information must be as efficient as possible, and as precise as possible. This forces one to make a tradeoff between efficiency and preciseness.
One traditional way of identifying stores into old objects is referred to as xe2x80x9ccard marking,xe2x80x9d wherein the heap is divided into fixed-size subsets and associated with each subset is a xe2x80x9ccard,xe2x80x9d i.e., a storage location. On every store into the portion of the heap that contains old objects, the card associated with the heap address stored into is marked. At collection time, the entire heap subset associated with all marked cards is scanned for pointers to new objects. A more detailed description of exemplary card marking schemes is set forth in Paul R. Wilson and Thomas G. Moher, xe2x80x9cA Card-Marking Scheme for Controlling Intergenerational References in Generation-Based GC on Stock Hardware,xe2x80x9d SIGPLAN Notices 24(5), pp. 87-92 1989, and Urs Holzle, xe2x80x9cA Fast Write Barrier for Generational Garbage Collectors,xe2x80x9d presented at OOPLSA ""93 Garbage Collection Workshop, Washington, D.C., October, 1993, available at http://www.sunlabs.com/research/self/papers/write-barrier.html, hereinafter incorporated by reference in their entirety.
The card marking scheme is efficient in two ways. First, the card marking is accomplished by a small number of shifts to find the card to be marked, and one store. In addition, if multiple stores into the same card are performed, at collection time the associated heap subset is scanned only once. However, at collection time, the entire heap subset for each marked card must be scanned rather than just the (possibly) one object stored into. In addition, some scheme for finding object boundaries in the heap is required, or else the scan must be conservative. The executing code may or may not be able to distinguish efficiently between stores of object pointers and stores of scalar values, in which case more cards will be marked than necessary. This effect always happens when the monitoring is done by hardware memory protection mechanisms, as it is in some proposals. Thus, in summary, the card marking imposes too much of a burden on the collection process in the interest of minimizing the cost for the first store of required information.
As an alternative to card marking, one can accumulate a buffer of pointers to objects which have been modified, and, more particularly, objects that have been modified by stores of pointers. The buffer may include the values stored as well as the addresses of the objects stored into. An exemplary buffer scheme is described in detail in xe2x80x9cA Comparative Performance Evaluation of Write Barrier Implementations,xe2x80x9d Antony L. Hosking, J. Eliot B. Moss and Darko Stefanovic, Proc. of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pp. 92-109 (Vancouver, Canada, October 1992). ACM SIGPLAN Notices 27(10), October 1992, available at http://osl-www.cs.umass.edu/, herein incorporated by reference in its entirety.
Compared to card marking, the buffer scheme is more costly to record, but is more precise. However, the buffer may become too large, because of duplicate entries (the same object being stored into more than once), and especially because of unnecessary recording of stores into young objects.
An additional overhead associated with maintaining remembered sets occurs when a young object survives enough garbage collections to be promoted to an older generation. At the time the object is promoted to an older generation, it must be determined if the object contains object references to objects in the younger generation. If the object does contain object references to objects in the younger generation, then the promoted object must be added to the remembered set for the younger generation.
A need therefore exists for a method and apparatus for efficiently managing remembered sets in a generational garbage collection scheme. Specifically, a need exists for an efficient mechanism for detecting when an old object has a pointer to a young object, and needs to be identified in the remembered set. In addition, a further need exists for an efficient mechanism for detecting when an object in the remembered set no longer contains a pointer to a young object, so that the object can be removed from the remembered set.
Generally, a method and apparatus are provided for the efficient management of remembered sets in a generational garbage collection scheme. In order to manage the remembered set, the present invention provides a first mechanism for detecting when an old object has a pointer to a young object, and needs to be added to the remembered set, and a second mechanism for detecting when an object already in the remembered set no longer contains a pointer to a young object, so that the object can be removed from the remembered set.
The present invention utilizes a write buffer and a temporary buffer to efficiently create and maintain the remembered set in a generational garbage collection scheme. Entries in the write and temporary buffers are used as part of the root set for creating the remembered set for the next garbage collection. Specifically, at the end of each garbage collection, entries in the write and temporary buffers are added to the remembered set for the next garbage collection if the objects satisfy the criterion for membership, i.e., they are live and may contain pointers to objects in a younger generation.
A barrier bit is associated with each object to differentiate generations in the generational garbage collection scheme. In the illustrative embodiment, the barrier bit is initially set to zero when the object is first created and the barrier bit is set to one when the object first survives a garbage collection. The barrier bit is used to determine whether to make an entry into a write buffer when a reference to another object is stored into an object. Specifically, an entry is made in the write buffer only if the barrier bit of the object that is written into is set.
The present invention establishes three general categories of generations in the generational garbage collection scheme. The youngest generation is comprised of objects that are first created and have not yet survived a garbage collection cycle. Objects that have survived one or more collections, but not the minimum number, N, of collections to be considered an old object are referred to herein as xe2x80x9cmiddle-agedxe2x80x9d objects. Thus, objects that have survived M garbage collection cycles, where M is between one and N garbage collections, are said to be middle-aged objects. Finally, objects that have survived N garbage collection cycles are said to be xe2x80x9coldxe2x80x9d objects.
The present invention uses the write buffer and barrier bit to monitor stores of object references into middle-aged or old objects. Middle-aged objects having an object reference which has been modified since the previous garbage collection will be identified in the write buffer. During a minor garbage collection, the write buffer and remembered set are scanned. Objects identified in the write buffer and remembered set are transferred to the remembered set if the object is an old object or a middle-aged object that is determined to be live. Middle-aged objects identified in the write buffer and remembered set that are not yet known to be live are transferred to the temporary buffer. At the end of the minor collection, the temporary buffer is processed, to transfer objects that are then known to be live into the remembered set. For middle-aged objects that are not live at the end of the minor collection, these objects are garbage and their storage is reclaimed.
A more complete understanding of the present invention, as well as further features and advantages of the present invention, will be obtained by reference to the following detailed description and drawings.